package sample.xiaosong.basicsort;

/**
 * @author xiaosong
 */
public class NodeBasic {

    public static Node preOrder(Node head) {
        Node pre = null;
        Node cur = head;
        while (cur != null) {
            Node temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public static ListNode preOrder(ListNode head, int m, int n) {
        ListNode mNodePre = null;
        ListNode nNodeNext = null;
        ListNode mNode = null;
        ListNode nNode = null;
        ListNode pre = null;
        ListNode cur = head;
        int nodeNum = 1;
        while (cur != null) {
            if (nodeNum < m) {
                cur = cur.next;
                nodeNum++;
                if (nodeNum == m - 1) {
                    mNodePre = cur;
                }
                continue;
            }
            if (nodeNum == m) {
                mNode = cur;
            }
            if (nodeNum == n) {
                nNode = cur;
            }
            if (nodeNum == n + 1) {
                nNodeNext = cur;
                break;
            }
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            nodeNum++;
        }
        mNodePre.next = nNode;
        mNode.next = nNodeNext;
        return pre;
    }

    public static ListNode postOrder(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = postOrder(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    public static void printCommonPart(Node head1, Node head2) {
        while (head1 != null && head2 != null) {
            if (head1.value < head2.value) {
                head1 = head1.next;
            } else if (head1.value > head2.value) {
                head2 = head2.next;
            } else {
                System.out.print(head1.value + " ");
                head1 = head1.next;
                head2 = head2.next;
            }
        }
    }

    public static boolean isPalindrome(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 慢指针
        Node slowNode = head;
        // 快指针
        Node fastNode = head;
        //分别表示奇数个和偶数个节点
        while (fastNode.next != null && fastNode.next.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        // 快指针移到右边区域的第一个节点
        fastNode = slowNode.next;
        // 左边区域最后一个节点切断
        slowNode.next = null;
        // 翻转右边区域的链表，并返回新的头节点
        Node rightHeadNode = preOrder(fastNode);
        Node saveNewHead = rightHeadNode;
        boolean result = true;
        Node leftHeadNode = head;
        while (leftHeadNode != null && rightHeadNode != null) {
            if (leftHeadNode.value != rightHeadNode.value) {
                result = false;
                break;
            }
            leftHeadNode = leftHeadNode.next;
            rightHeadNode = rightHeadNode.next;
        }
        // 再次翻转右边区域的链表，并返回新的头节点
        // 还原链表
        slowNode.next = preOrder(saveNewHead);
        return result;
    }

    public static Node listPartition(Node head, int pivot) {
        Node SH = null; //小于区域头节点
        Node ST = null; //小于区域尾结点
        Node EH = null; //等于区域头节点
        Node ET = null; //等于区域尾结点
        Node BH = null; //大于区域头结点
        Node BT = null; //大于区域尾结点
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (SH == null) {
                    SH = head;
                } else {
                    ST.next = head;
                }
                ST = head;
            } else if (head.value == pivot) {
                if (EH == null) {
                    EH = head;
                } else {
                    ET.next = head;
                }
                ET = head;
            } else {
                if (BH == null) {
                    BH = head;
                } else {
                    BT.next = head;
                }
                BT = head;
            }
            head = next;
        }
        // 小于区域存在
        if (ST != null) {
            ST.next = EH;
            ET = ET == null ? ST : ET;
        }
        if (ET != null) {
            ET.next = BH;
        }
        return SH != null ? SH : EH != null ? EH : BH;
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node node1 = new Node(2);
        node1.next = new Node(3);
        node1.next.next = new Node(5);
        node1.next.next.next = new Node(6);

        Node node2 = new Node(1);
        node2.next = new Node(2);
        node2.next.next = new Node(5);
        node2.next.next.next = new Node(7);
        node2.next.next.next.next = new Node(8);

        printLinkedList(node1);
        printLinkedList(node2);
        printCommonPart(node1, node2);


        Node head = null;
        printLinkedList(head);
        System.out.println(isPalindrome(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        printLinkedList(head);
        System.out.println(isPalindrome(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        printLinkedList(head);
        System.out.println(isPalindrome(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(1);
        printLinkedList(head);
        System.out.println(isPalindrome(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        printLinkedList(head);
        System.out.println(isPalindrome(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(1);
        printLinkedList(head);
        System.out.println(isPalindrome(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.println(isPalindrome(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.println(isPalindrome(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(2);
        head.next.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.println(isPalindrome(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

    }

    public static class Node {
        public int value;
        public Node next;
        public Node(int data) {
            this.value = data;
        }
    }
}

/**
 * 单链表节点的结构
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    ListNode(){}
}
